#ifndef 单链表
#define 单链表

#include <sstream>
#include <cstdlib>
#include <sstream>
#include <iostream>

typedef int ElemType;

typedef struct LNode
{
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

LinkList List_HeadInsert(LinkList &L, const std::string &example)
{
    int x;
    LNode *s;
    L = new LNode;

    L->data = 0, L->next = nullptr;

    std::stringstream ss(example);
    ss >> x;
    while (x != 9999)
    {
        s = new LNode;
        s->data = x;
        s->next = L->next;
        L->next = s;
        L->data++;
        ss >> x;
    }
    ss.clear();
    return L;
}

LinkList List_TailInsert(LinkList &L, const std::string &example)
{
    L = new LNode;
    L->data = 0;
    L->next = nullptr;
    LNode *s = L;
    int x;
    std::stringstream ss(example);
    ss >> x;
    while (x != 9999)
    {
        s->next = new LNode;
        s->next->data = x;
        s = s->next;
        L->data++;
        ss >> x;
    }
    ss.clear();
    s->next = nullptr;
    return L;
}

/**
 * @brief 获取第 i 个结点，从1开始
 * @param L 链表
 * @param i 位置
 * @return 该结点指针
 */
LNode *GetElem(LinkList L, int i)
{
    if (i < 1 or i > L->data)
        return nullptr;

    int index = 0;
    LNode *p = L->next;
    while (++index != i)
        p = p->next;
    return p;
}

/**
 * @brief 查找第一个值与 e 相同的结点
 * @param L 链表
 * @param e 需要查找的值
 * @return 第一个结点
 */
LNode *LocateElem(LinkList L, ElemType e)
{
    LNode *s = L->next;
    while (s != nullptr and s->data != e)
        s = s->next;
    return s;
}

LNode *ListInsert(LinkList &L, int i, ElemType e)
{
    LNode *s = new LNode;
    LNode *p = nullptr;
    s->data = e;
    if (i != 1)
    {
        p = GetElem(L, i - 1);
        if (p == nullptr)
            return nullptr;
    }
    else
        p = L;

    s->next = p->next;
    p->next = s;
    L->data++;
    return s;
}

LNode *ListDelete(LinkList &L, int i)
{
    LNode *p;
    if (i != 1)
    {
        p = GetElem(L, i - 1);
        if (p == nullptr)
            return nullptr;
    }
    else
        p = L;
    
    LNode *s = p->next;
    p->next = p->next->next;
    L->data--;
    delete s;

    return p->next;
}

int Length(LinkList &L)
{
    return L->data;
}

#endif